The present invention relates to Translation Look-Aside Buffers (TLB).
Many modern data processing units rely on a virtual to physical address mapping for establishing and managing the distinction between a user's view of memory and the actual physical manifestation of that memory.
For a variety of reasons, it is desirable that the page size be different for specific uses of the processor or even within a single use for different regions within the memory space. The page size is the portion of an address which remains unmapped in the translation from virtual to physical address through the TLB. An incomplete but representative list of these reasons is as follows:
(1) The "best" page size can be a function of the specific operating system which is being used. This might be particularly true when considering different types of operating systems such as general purpose, real time, embedded control, etc. It might also be true, however, for different general purpose operating systems.
(2) Even within one operating system, it is often desirable to have different page sizes for different regions of memory. In particular, while a typical user process desires a small to medium page size, say four to sixteen kilobytes, a process which is responsible for updating a bit-mapped display terminal desires a very large page size, generally greater than one megabyte.
(3) In a similar vein, a less typical but very important application such as a scientific program with a very large data space desires a medium to large page size in order to "reach" all of its data without excessive overhead due to "misses" in the TLB. The desired page size in this case could be in the sixty-four kilobyte to one megabyte range.
(4) As a final example, the operating system itself needs to be able to access all of the memory space and for performance reasons it is necessary that it not use a large number of TLB entries for this purpose since they are then not available to the user processes. The operating system therefore desires to map all of memory using only a few very large pages.
Two other parameters of interest when specifying a TLB are the degree of associativity and the number of entries.
The degree of associativity can range from no associativity, typically referred to as direct mapped, to fully associative. Typical implementations use no less than degree four associativity, called four way set associative, and many implementations are fully associative. The higher the degree of associativity the less chance there is for mapping collisions: i.e., two or more physical addresses which cannot be co-resident in the TLB because they have the same value for the portion of the address which is used to index into the TLB. In a two way set TLB it is possible to have two entries with the same index, four way can have four, and so on up to fully associative where there is no index and any entry can map any address. All other things being equal, fully associative is the most desirable.
The number of entries is simply the number of different virtual to physical mappings that the TLB can maintain at any one time. This number is determined almost purely by the physical size of the TLB measured in number of components or printed circuit board area or silicon area, etc.
In processors implemented in full custom VLSI, it is quite feasible to build a fully associative TLB. This is true primarily due to the degree of regularity which can be achieved in a fully associative implementation. There are essentially only two distinct parts to the TLB. The content addressable memory, or CAM portion and the physical storage portion. This contrasts with a set associative implementation which has five parts: an index decoder, a virtual storage portion, a comparator portion, a selection portion, and a physical storage portion. In essence, the fully associative implementation combines the first four pieces of the set associative implementation into a single CAM array.